#leetcode题目90：子集II
#难度：中等

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        def dfs(index, nums, path, res):
            res.append(path[:])
            for i in range(index, len(nums)):
                if i > index and nums[i] == nums[i-1]:
                    continue
                path.append(nums[i])
                dfs(i+1, nums, path, res)
                path.pop()
        res = []
        dfs(0, nums, [], res)
        return res


#测试数据
nums = [1,2,2]
#预期输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
solution = Solution()
print(solution.subsetsWithDup(nums))

nums = [0]
#预期输出：[[],[0]]
solution = Solution()
print(solution.subsetsWithDup(nums))